#include <bits/stdc++.h>

using namespace std;

int n,m,dp[1010],c[1010][1010],v[1010][1010],num[1010],jd;
int main()
{
    cin>>m>>n;
    for(int i=1;i<=n;i++){
        int t1,t2,t3;
        cin>>t1>>t2>>t3;
        jd = max(jd,t3);
        num[t3]++;
        c[t3][num[t3]] = t1;
        v[t3][num[t3]] = t2;
    }
    for(int i=1;i<=jd;i++){
        for(int j=m;j>=0;j--){
            int maxv=-1;
            for(int k=1;k<=num[i];k++){
                if(j>=c[i][k])
                maxv=max(dp[j-c[i][k]]+v[i][k],maxv);
            }
            dp[j] = max(dp[j],maxv);
        }
    }
    cout<<dp[m];
    return 0;
}
